/*
 * Copyright (C), 2015-2018
 * FileName: Solution019
 * Author:   zhao
 * Date:     2018/11/19 21:11
 * Description: 19. 删除链表的倒数第N个节点
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

import com.lizhaoblog.diynode.ListNode;

/**
 * 〈一句话功能简述〉<br>
 * 〈19. 删除链表的倒数第N个节点〉
 *
 * @author zhao
 * @date 2018/11/19 21:11
 * @since 1.0.1
 */
public class Solution019 {

    /**************************************
     * 题目
     给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
     示例：
     给定一个链表: 1->2->3->4->5, 和 n = 2.

     当删除了倒数第二个节点后，链表变为 1->2->3->5.
     说明：
     给定的 n 保证是有效的。
     进阶：
     你能尝试使用一趟扫描实现吗？
     **************************************/

    /**************************************
     *
     * 想法：
     *          1. 空间换时间的做法
     *              用一个长度为n+1的数组接收节点
     *              不过需要实时更新数组，有点复杂
     *              时间复杂度为n，空间复杂度为n
     *          2. 遍历2次法
     *              先循环一次，算出长度，不过扫描了2次，不符合题目
     *          3. 双指针法
     *              搞2个指针，让AB指针中间间隔为n+1，这样A到末尾的时候，B的下一个节点刚好就是要删掉的东西
     *
     * 我的做法
     *      超过99%的测试案例
     *      时间复杂度：n
     *      空间复杂度：1
     * 代码执行过程：
     *
     * 总结：
     *      遇到链表没有第一时间想到双指针
     *      空间换时间，虽然可以做出来，但是很操蛋
     *
     * ***********************************/
    public ListNode removeNthFromEnd(ListNode head, int n) {

        if (head == null || n == 0) {
            return head;
        }

        ListNode ANode = head;
        ListNode BNode = head;

        for (int i = 0; i < n; i++) {
            ANode = ANode.next;
        }
        while (ANode == null) {
            ANode = ANode.next;
            BNode = BNode.next;
        }

        if (n == 1) {
            BNode.next = null;
        } else {
            BNode.next = BNode.next.next;
        }

        return head;
    }

    /**************************************
     * 比我好的答案 better
     * ***********************************/
    public ListNode better(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        int length = 0;
        ListNode first = head;
        while (first != null) {
            length++;
            first = first.next;
        }
        length -= n;
        first = dummy;
        while (length > 0) {
            length--;
            first = first.next;
        }
        first.next = first.next.next;
        return dummy.next;
    }

}
